#ifndef _SLM_H_
#define _SLM_H_

#include "port.h"

class CBuilder;

class CSlm {
  friend class CBuilder;
public:
  typedef unsigned int TFREQ;
  typedef float TPROB;

  struct TLeaf {
    TWORDID id;
    union {
      TFREQ freq;
      TPROB pr;
    };
  public:
    TLeaf(TWORDID theId = 0, TFREQ fr = 0): id(theId), freq(fr)
      { }
    bool operator < (const TLeaf &r) const
      { return id < r.id;}
    bool operator > (const TLeaf &r) const
      { return id > r.id;}
    bool operator == (const TLeaf &r) const
      { return id == r.id;}
  };

  struct TNode : public TLeaf {
    int child;
    TPROB bow;
  public:
    TNode(TWORDID theId = 0, int ch = 0, TFREQ fr = 0, TPROB theBow = 0.0)
      : TLeaf(theId, fr), child(ch), bow(theBow)
      {}
  };

public:
  bool Load(const char *fname);
  void Free();

  unsigned int
  isUseLogPr()                  // Use Logarithm represent
    {return bUseLogPr;}
  double getPr(int n, TWORDID *hw);
  double getNegLogPr(int n, TWORDID *hw);

  CSlm() : N(0), sz(NULL), level(NULL), bUseLogPr(0) {}

protected:
  double getPrAsLog(int n, TWORDID *hw);
  double getPrDirect(int n , TWORDID *hw);

protected:
  int N;
  unsigned int bUseLogPr;
  int *sz;
  void **level;
};

template <class _NodeT_>
_NodeT_ *binary_find(_NodeT_ *base, int h, int t, const _NodeT_ &val) {
  while (h < t) {
    int m = (h + t) / 2;
    _NodeT_ *pm = base + m;
    if (*pm < val)
      h = m + 1;
    else if (*pm > val)
      t = m;
    else
      return pm;
  }
  return NULL;
}

template <class _NodeT_>
_NodeT_ binary_find_id(_NodeT_ *ph, _NodeT_ *pt, TWORDID id) {
  int h = 0, t = pt - ph;
  while (h < t) {
    int m = (h + t) / 2;
    _NodeT_ *pm = ph + m;
    if (pm->id == id)
      return pm;
    else if(pm->id < id)
      h = m + 1;
    else
      t = m;
  }
  return NULL;
}

#endif /* _SLM_H_ */
